package demo24;

/*
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 */

public class Test {
    public static void main(String[] args) {

        ListNode ln = new ListNode(1);
        ListNode l1 = ln;
        for (int i = 2; i < 5; i++) {
            ln.next = new ListNode(i);
            ln = ln.next;
        }

        ListNode result = swapPairs(l1);
        while (result != null){
            System.out.println(result.val);
            result = result.next;
        }

    }


    public static ListNode swapPairs(ListNode head) {
        ListNode result = head;
        ListNode exchange = null, left = null, right = null;
        //是否是第一次进行节点交换
        boolean isFirst = true;
        while(head != null && head.next != null){
            //循环，每次交换相邻节点
            //获取左右节点
            left = head;
            right = head.next;
            //移动head，移动两步
            head = head.next.next;
            if(!isFirst){
               //如果不是第一次交换节点，那么一定在left节点的左边还有一个节点
               //将这个节点保存下来，给下一次循环的时候指向left
               exchange.next = right;
            }else{
                isFirst = false;
                //获取最终结果的起点
                result = right;
            }
            //将左节点给更左边的指向
            //将右节点指向左节点
            right.next = left;
            //将左节点保存进exchange，让他指向下一轮的left
            exchange = left;
        }
        if(!isFirst && head != null){
            //循环结束后，如果剩下一个没有凑对的节点，将左节点与他连接即可
            left.next = head;
        }else if(!isFirst && head == null){
            //如果没有节点，也就是说全部都凑对了，那么左节点的下一个节点置空即可
            left.next = null;
        }
        return result;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}